package kyssion.leetcode.num1_50;

import kyssion.leetcode.util.ListNode;

/**
 * 给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
 * <p>
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
 * <p>
 * 示例 :
 * <p>
 * 给定这个链表：1->2->3->4->5
 * <p>
 * 当 k = 2 时，应当返回: 2->1->4->3->5
 * <p>
 * 当 k = 3 时，应当返回: 3->2->1->4->5
 * <p>
 * 说明 :
 * <p>
 * 你的算法只能使用常数的额外空间。
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 */
public class code25_k个一组旋转列表 {
    public static void main(String[] args) {
        ListNode listNode = new code25_k个一组旋转列表().reverseKGroup2(
                ListNode.createListNode(new int[]{
                        1, 2, 3, 4, 5, 6, 7, 8, 9, 10
                }), 3
        );
        ListNode.showListNode(listNode);

    }

    /**
     * 方法1 正向思维,先筛选出开始位置和结束位置,然后将中间的节点进行转至即可
     *
     * @param i
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode i, int k) {
        ListNode head = new ListNode(-1);
        head.next = i;
        ListNode nowNode = head;
        while (nowNode != null) {
            int times = 0;
            ListNode before = nowNode;
            ListNode start = before.next;
            while (times < k && nowNode.next != null) {
                nowNode = nowNode.next;
                times++;
            }
            if (times != k) {
                break;
            }
            ListNode next = nowNode.next;
            before.next = reverse(start, k);
            start.next = next;
            nowNode = start;
        }
        return head.next;
    }

    public ListNode reverse(ListNode node, int length) {
        ListNode before = node;
        ListNode next = node.next;
        int time = 1;
        while (next != null && time < length) {
            ListNode nextOne = next.next;
            next.next = before;
            before = next;
            next = nextOne;
            time++;
        }
        return before;
    }

    /**
     * 2. 方法2 使用插入的方法实现倒序 , 其实也没有什么本质上的优化这里就省略一下吧
     * 1 2 3 4
     */
    public ListNode reverseKGroup2(ListNode i, int k) {
        ListNode head = new ListNode(-1);
        head.next = i;
        ListNode nowNode = head;
        ListNode titleNode = nowNode.next;
        int index = 1;
        while (nowNode.next != null && index < k) {
            ListNode insertNode = titleNode.next;
            if (insertNode == null) {
                break;
            }
            ListNode nextInsertNode = insertNode.next;
            insertNode.next = nowNode.next;
            nowNode.next = insertNode;
            titleNode.next = nextInsertNode;
            index++;
        }
        return head.next;
    }
}
